﻿using System;
using System.Collections.Generic;

namespace ProjectEulerIssues
{
	public partial class Program
	{
		[SolutionInfo(Links = "http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion")]
		public static dynamic Problem64()
		{
			const int LIMIT = 10000;

			Func<long> solve = () => 
			{
				int oddPeriodCount = 0;

				for (int n = 2; n <= LIMIT; n++)
				{
					int a0 = (int)Math.Sqrt(n);
					if (a0 * a0 == n)
					{
						continue;
					}
					int a = a0;
					int d = 1;
					int m = 0;
					var pHash = new HashSet<string>();
					var key = string.Format("{0}-{1}-{2}", a0, d, m);
					pHash.Add(key);
					int periodLength = 0;
					while (true)
					{
						m = d * a - m;
						d = (n - m * m) / d;
						a = (a0 + m) / d;
						key = string.Format("{0}-{1}-{2}", a, d, m);
						if (pHash.Contains(key))
						{
							break;
						}
						pHash.Add(key);
						periodLength++;
					}
					if (periodLength % 2 == 1)
					{
						oddPeriodCount++;
					}
				}
				return oddPeriodCount;
			};
			return solve();
		}
	}
}
